

#include <iostream>
#include <algorithm>
#include <array>
using namespace std;


namespace fengxw
{

template<class T>
bool less(const T& a , const T& b)
{
	return a<b?true:false;
}


template<class T ,std::size_t N>
void merge( array<T,N>&  a , array<T,N>&  aux ,int lo ,int mid , int hi)
{
	//将 a[lo ..mid] and a[mid+1...hi] merge
	int  i = lo; 
	int  j = mid +1;

	if(hi>=N)
	{
		std::cout<<"Fatal Error! hi is big and equal N"<<endl;
		return;
	}

	for(int k=lo; k<=hi; k++)
		aux[k] = a[k];


	for(int k=lo; k<=hi; k++)
	{
		if(i > mid)
		{
			a[k] = aux[j++];
		}else if(j > hi)
		{
			a[k] = aux[i++];
		}else if(fengxw::less(aux[j] , aux[i] ))
		{
			a[k] = aux[j++];
		}else{
			a[k] = aux[i++];
		}
	}

	return;
}


template<class T , size_t N>
void out(const array<T ,N>& a)
{
	for(int i=0; i<N; i++)
	{
		if(0==i)
		{
			std::cout<<"( "<<a[i]<<" , ";
		}else if(N==(i+1))
		{
			std::cout<<a[i]<<" )"<<endl;
		}else {
			std::cout<<a[i]<<" , ";	
		}
	}
}
};
